using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Contracts;

namespace Tycho.Parser.Peg {
    /// <summary>
    /// This implements the algorithm found in the paper Packrats Can Support Left Recursion
    /// which you can read here http://www.vpri.org/pdf/tr2007002_packrat.pdf.
    /// 
    /// The only difference being that I've implemented a stack of HEADs for each POSITION, the paper
    /// suggests you only need one HEAD for each POSITION. See section 3.4.
    /// 
    /// The reason for this is that if we have a grammar with more than one left recursive non-terminal,
    /// and one invokes the other, the second one needs to be treated as the current left recursive
    /// production, and when that's finished, the first needs to be treated as the current left
    /// recursive production again. Well, at any rate, I found that it didn't work without it.
    /// </summary>
    public class LeftRecursionInformation {
        class Recursion {
            public readonly HashSet<IProduction> InvolvedProductions;
            public readonly IProduction CurrentRecursiveProduction;

            public Recursion (IProduction currentRecursiveProduction, HashSet<IProduction> involvedProductions) {
                InvolvedProductions = involvedProductions;
                CurrentRecursiveProduction = currentRecursiveProduction;
            }
        }

        private readonly Stack<ProductionInvocation> _productionInvocationStack;
        public readonly ParseResult RecursiveResult;
        private readonly Dictionary<int, Stack<Recursion>> Recursions;

        public LeftRecursionInformation () {
            _productionInvocationStack = new Stack<ProductionInvocation> ();
            RecursiveResult = new ParseResult (0, null, null);
            Recursions = new Dictionary<int, Stack<Recursion>> ();
        }

        public IEnumerable<ProductionInvocation> ProductionInvocationStack {
            get {
                return _productionInvocationStack.ToArray ();
            }
        }

        public void DeclareRecursiveParse (IProduction production, int index) {
            var involved = _productionInvocationStack
                .TakeWhile (p => p.Production != production)
                .Where (p => p.Index == index)
                .Select (p => p.Production);

            SetCurrentRecursiveParse (production, index, involved);
        }

        private void SetCurrentRecursiveParse (IProduction production, int index, IEnumerable<IProduction> involved) {
            Stack<Recursion> recursions;
            if (Recursions.TryGetValue (index, out recursions)) {
                var mostRecentRecursion = recursions.Peek ();
                if (mostRecentRecursion.CurrentRecursiveProduction == production) {
                    mostRecentRecursion.InvolvedProductions.UnionWith (involved);
                } else {
                    recursions.Push (new Recursion (production, new HashSet<IProduction> (involved)));
                }
            } else {
                var recursion = new Recursion (production, new HashSet<IProduction> (involved));
                recursions = new Stack<Recursion> ();
                recursions.Push (recursion);
                Recursions.Add (index, recursions);
            }
        }

        public bool IsInvolvedInRecursion (IProduction production, int index) {
            Stack<Recursion> recursions;
            if (Recursions.TryGetValue (index, out recursions)) {
                return recursions.Peek ().InvolvedProductions.Contains (production);
            } else {
                return false;
            }
        }

        public bool IsRecursiveProduction (IProduction production, int index) {
            Stack<Recursion> recursions;
            if (Recursions.TryGetValue (index, out recursions)) {
                return recursions.Peek ().CurrentRecursiveProduction == production;
            } else {
                return false;
            }
        }

        public void BeginParsing (IProduction p, int index) {
            var key = new ProductionInvocation (p, index);
            _productionInvocationStack.Push (key);
        }

        public void EndParsing () {
            _productionInvocationStack.Pop ();
        }

        public bool CurrentlyParsing (IProduction production, int index) {
            return _productionInvocationStack.Contains (new ProductionInvocation (production, index));
        }

        public void CompletedRecursiveParse (int index) {
            Stack<Recursion> recursions;
            if (Recursions.TryGetValue (index, out recursions)) {
                recursions.Pop ();
                if (recursions.Count == 0) {
                    Recursions.Remove (index);
                }
            }
        }

        public void ClearInvolvedProductions(char[] source, int index)
        {
            Stack<Recursion> recursions;
            if (Recursions.TryGetValue (index, out recursions)) {
                HashSet<IProduction> involvedProductions = recursions.Peek ().InvolvedProductions;

                foreach (var involvedProduction in involvedProductions)
                {
                    involvedProduction.GetMemoTable(source).Remove(index);
                }
            }
        }
    }
}